Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Gut, können wir anfangen?

Gut, ich nehme an, ihr wurdet vorgewarnt, dass Professor Kohlhäuser heute halt leider nicht da ist.

Der ist auf einer Konferenz in Wien. Deswegen müsst ihr euch jetzt mit mir zufriedengeben.

Ich bin mir nicht so ganz sicher, was genau ihr alles gestern gemacht habt.

Ich bin mir ziemlich sicher, dass ihr damit angefangen habt.

Also ich weiß, wo ihr aufgehört habt. Ich weiß noch nicht, wo ihr angefangen habt.

Gut. Dann mache ich mal Recap einfach über den gesamten Informed-Gramm.

Ich nehme an, der Uninformed ist euch sowieso noch hinreichend im Gedächtnis.

Zumindest wenn ihr euch mal die Übungsblätter angeschaut habt oder so.

Gut. Also worum geht es jetzt in Informed Search im Vergleich zu Uninformed?

Also die Kernidee ist einfach nur, dass ich in irgendeiner Art und Weise versuche,

zusätzliches Wissen, das ich über das Problem, das ich versuche zu lösen, habe, mit reinzubringen.

Was wir eigentlich ausschließlich über Heuristiken machen.

Einfachste Variante ist natürlich einfach Pre-Desearch.

Worum geht es da? Na ja, ich bastle mir irgendeine Evaluationsfunktion,

was im Prinzip auch sowas wie eine Heuristik ist.

Und gucke dann einfach nur, welcher Knoten sieht irgendwie am sinnvollsten aus unter dieser Evaluierung.

Den Fringe muss ich dann einfach nur noch in Bezug auf die Evaluationsfunktion sortieren.

Und dann renne ich halt einfach in die Richtung, die irgendwie am sinnvollsten aussieht.

Ich glaube, das ist Dykstra, oder? Weiß das jemand? Oder war Dykstra was anderes?

Ich kann mir die Namen immer nicht merken.

Dykstra ist Uninformed Search.

Bitte? Dykstra ist Uninformed Search.

Ah, langweilig. Ok. Schade. Gut, dann ist das einfach Pre-D. Dann vergesst, was ich gerade gesagt habe.

Wie machen wir das? Na ja, ok. Was wir eigentlich wollen, ist halt eben, wir definieren jetzt erstmal Heuristik.

In dem Fall verlangen wir, das ist noch gar nicht die richtige Definition.

Da kommt noch eine andere, ne? Ja, Tatsache.

Gut, also in dem Fall ist es einfach nur eine Evaluationsfunktion, was wir letzten Endes wollen.

Insbesondere bei A star ist natürlich, dass die Heuristik null ist, wenn wir bereits einen Zielknoten erlangt haben.

Sonst macht ihr irgendwie nicht das, was ihr eigentlich soll.

Aber ok, was heißt das Ganze jetzt? Na ja, nehmen wir unser klassisches Beispiel, was schon die ganze Zeit rankam.

Wir sind irgendwo in Rumänien und wir wollen irgendwie nach Bukarest kommen von, wo fangen wir an?

Ovadia, ne? Arad. Wo ist denn Arad?

Ah, da, genau. Wenn wir irgendwie dahin wollen, ja ok.

Unser Ziel ist es natürlich, den Pfad dahin zu finden.

Wie lang der ist oder sowas wissen wir nicht genau, bevor wir nicht den Idealen gefunden haben.

Aber was wir auf jeden Fall mal irgendwie machen können, ist halt einfach Fluglinie.

Und das als Abschätzung nehmen.

Wenn wir das als Heuristik nehmen, dann hilft uns das schon extrem.

Dann gucken wir einfach nur noch, welcher Knoten ist denn irgendwie so da, wo wir hin wollen.

Ziehen wir das hier mal durch. Ja, eins, zwei, drei, nach drei Expansionen sofort da angekommen, wo wir hin wollen.

Wunderbar.

Also so viel zu Greedy Search. Hier nochmal dasselbe, wenn man einfach die Manhattan Distance nimmt auf einem Rectangular Grid.

Übrigens eine dieser Heuristiken, die ständig auftauchen werden in Manhattan.

Was passiert dann? Ja, ok, wir finden halt tatsächlich, also es ist jetzt hier nicht eingezeichnet, aber ne.

Man muss ja nur gucken, wo wir jetzt immer am kleinsten.

Also es ist nicht eindeutig, es gibt mehrere Pfade, aber letzten Endes sind die alle gleich lang.

Und das geht mehr oder minder auf den ersten Anhieb.

In dieser Art von Problemen natürlich.